package com.demo.java.OD151_200.OD160;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【连续子串】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145765370
 */
public class OdMain {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            String t = s.nextLine(); // 输入字符串 t
            String p = s.nextLine(); // 输入字符串 p
            solveMethod(t, p); // 调用解决方法
        }
    }

    // 解决字符串匹配问题的主方法
    private static void solveMethod(String t, String p) {
        int[] lps = computeLPS(p); // 计算部分匹配表
        int i = 0, j = 0; // i 是 t 中的指针，j 是 p 中的指针
        while (i < t.length()) {
            // 如果字符匹配
            if (t.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            }
            // 如果 j 达到 p 的长度，表示找到一个匹配
            if (j == p.length()) {
                System.out.println(i - j + 1); // 输出匹配的起始位置（从 1 开始）
                return;
            } else if (i < t.length() && t.charAt(i) != p.charAt(j)) {
                // 如果字符不匹配，使用 LPS 跳过不必要的比较
                if (j != 0) {
                    j = lps[j - 1]; // 跳到前一个可能的匹配位置
                } else {
                    i++; // 继续向前移动 t 的指针
                }
            }
        }
        System.out.println("No"); // 如果没有匹配，输出 "No"
    }

    // 计算部分匹配表（LPS 数组）
    private static int[] computeLPS(String p) {
        int[] lps = new int[p.length()];
        int len = 0, i = 1; // len 是当前最长的前后缀长度
        while (i < p.length()) {
            if (p.charAt(i) == p.charAt(len)) {
                len++;
                lps[i] = len; // 更新 LPS 数组
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // 如果不匹配，跳到上一个前后缀位置
                } else {
                    lps[i] = 0; // 如果没有前后缀，LPS 数组为 0
                    i++;
                }
            }
        }
        return lps;
    }
}